package ch5.index_count;

import java.util.Arrays;

/**
 * @author : DuJiabao
 * @Date : 2021/2/7 21:51
 * @Project : sword-finger-offer
 * @File : null.java
 * @Desc : 键索引计数法
 * 实现类别分组，且不破坏原始顺序！真的牛逼！
 */
public class Solution {
  public static void main(String[] args) {
    User[] users = userGenerator();
    int[] count = new int[6];  // 创建一个用来计数的数组（一共4组，但是用了6个位置，有巧妙）
    for (User user : users) {
      count[user.group + 1]++;  // 组号+1的位置，计数加一
    }
    for (int i = 0; i < count.length - 1; i++) {
      // 每个组的数，叠加前一个组以及更前面的组数，进而知道了自己组员的起始位置。比如，第二组，i=2， 前面有count[2](之前第一组的人数保存在这)个人，就是自己的起始索引
      count[i + 1] += count[i];
    }

    User[] aux = new User[15];
    for (User user : users) {
      // user.group 找出指定user的组别。count[user.group]找出该组别的开始索引位置。++实现索引后移，以供后续使用。aux[索引] = user，实现引用指定user
      aux[count[user.group]++] = user;
    }

    System.out.println(Arrays.toString(aux));

  }

  private static User[] userGenerator() {
    User[] users = new User[15];
    users[0] = new User("Anderson", 2);
    users[1] = new User("Brown", 3);
    users[2] = new User("Davis", 3);
    users[3] = new User("Garcia", 4);
    users[4] = new User("Harris", 1);
    users[5] = new User("Jackson", 3);
    users[6] = new User("Johnson", 4);
    users[7] = new User("Jones", 3);
    users[8] = new User("Martinez", 1);
    users[9] = new User("Miller", 2);
    users[10] = new User("Moore", 4);
    users[11] = new User("Robinson", 1);
    users[12] = new User("Smith", 2);
    users[13] = new User("Taylor", 1);
    users[14] = new User("Thomas", 4);
    return users;
  }

}
